package com.ztom.top100;

/**
 * 回文链表
 * <p>
 * https://leetcode-cn.com/problems/palindrome-linked-list/
 *
 * @author ZhangTao
 */
public class Code66IsPalindrome {

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }


    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return false;
        }
        if (head.next == null) {
            return true;
        }

        // 快慢指针: 慢指针一边走一遍逆序
        ListNode slow = head, fast = head;
        ListNode pre = null, prePre = null;
        while (fast != null && fast.next != null) {
            prePre = pre;
            pre = slow;

            slow = slow.next;
            fast = fast.next.next;

            pre.next = prePre;
        }
        if (fast != null) {
            // 奇数情况下, 跳过中间点
            slow = slow.next;
        }

        // 找到中点, 左部分一边比较一边复原链表
        ListNode left = pre;
        pre = null;
        prePre = null;
        while (left != null && slow != null) {
            if (left.val != slow.val) {
                return false;
            }
            slow = slow.next;

            prePre = pre;
            pre = left;
            left = left.next;
            pre.next = prePre;
        }
        return true;
    }
}
